Navigation Satellite Systems use the Aeronautical Radio Navigation Systems (ARNS) and Radio Navigation Satellite Systems (RNSS) wireless bands to provide protected ranging signals by which a specialised wireless receiver determines the location of its antenna. The Global Positioning System (GPS) is one example of a deployed Global Navigation Satellite System (GNSS).
GPS comprises space, control and user segments. The space segment consists of a number of orbiting satellites (otherwise known as space vehicles; SVs), each emitting several ranging signals, and the signals from several satellites are used together to determine the locations of the many receivers used in the control and user segments. The control segment measures the ranging signals from the visible constellation of satellites and uses the data to determine the historic orbits of the satellites in the constellation. The algorithms also use information about forces which each satellite experiences in order to form models describing the near-term future orbital behaviour of each satellite. The orbit predictions are converted into a set of parameters describing a close approximation to the orbit. The parameters are transmitted to each satellite and stored in the internal satellite memory for subsequent retransmission by the satellite during their period of validity. Each set of orbit prediction parameters relates to a specific part of the orbit which these model with least error. Such parameters are generally known as the ephemeris parameters. For GPS and Galileo, another GNSS system under development, a modified Kepler model is used as the basis for the parameter set.
The satellites also transmit clock parameters describing the behaviour of the atomic clock which is carried by each satellite. The drift of the satellite clock with respect to the GPS time reference is described by a three-parameter model comprising the satellite clock time offset from the global time reference for the GNSS system, a drift rate, and a drift acceleration parameter. For GPS, the global time reference time is held, at least, in an ensemble of clocks, some of which are located at the United States Naval Observatory in Washington, D.C.
The operation of the GPS satellite navigation system will now be described as an example of a GNSS system to which the current invention relates. The space segment consists of a minimum constellation of 27 active satellite and some active spares, totaling 31 satellites in October 2007. Whilst satellites have a design lifetime exceeding 7 years, many achieve longer lifetimes before failures lead to loss of control or function. The average life of satellites in the current constellation is approximately 8.7 years. The satellites are located in 6 orbital planes inclined at 55° to the Earth's equatorial plane. Each satellite executes an orbit in 12 hours sidereal time (not Earth's solar time scale). In ideal circumstances, satellites would be positioned in a regular angular disposition around each orbit, that is every 72°, but in practice active spare satellites are often purposefully pre-positioned close to ones expected to fail in the near term.
GPS receivers determine their positions by computing time delays between transmission and reception of signals transmitted from the satellites and received by the receiver on or near the surface of the Earth. The transmission time delays (through multiplication by the speed of radio waves) provide good approximations to the distances between a receiver and the respective satellite. Each satellite broadcasts a ranging signal, in the form of a direct-sequence spread-spectrum code, which serves both to identify the satellite and to carry pre-determined epochs in each satellite. The epochs are events associated with the transition of the satellite code generators to a specific state in the code sequence. The epochs serve to identify the time of transmission of a signal. The receiver uses the epoch to establish the instant of reception with respect to a local receiver clock.
GPS satellites also broadcast a data message containing the ephemeris parameters for each satellite orbit, and the satellite clock correction parameters. The data message includes a time message (for example, the so-called z-count in GPS) which identifies the transmission time (according to the satellite clock) of a specific event or identifiable epoch in the satellite broadcast. This data is included in the hand-over word (HOW) in the Coarse/Acquisition (C/A) message. The z-count identifies the instant of time corresponding to the data-bit transition at the start of the next sub-frame of data. This time signal allows the receiver to determine unambiguously a time-tag for the time of reception of this event. By knowing the corresponding time of transmission of each of the signals, the receiver can determine the range to the satellite, whilst also using the ephemeris data to calculate the satellite's position when it transmitted its signal. Finally, the receiver combines the knowledge of satellite positions with the determined ranges to calculate the receiver's position.
Each satellite transmits ranging signals as binary phase-shift keyed (BPSK) modulation on a carrier component. The ranging signals are characterised by a spreading code of known duration for which a replica (known herein as a satellite code replica) can be generated in a receiver. For each element of the spreading code, a spreading symbol is transmitted whose binary sign is determined by the state of the spreading code for the specific time of transmission. The spreading symbol is a rectangular pulse for signals such as the GPS C/A code and the GPS encrypted precise (P(Y)) code. New signals include the so-called L2CM/CL codes and M-codes, for which the spreading symbols are different. The large difference between the message-data rate (tens of Hertz) and spreading-code rate (MHz) permits the use of phase-shift keying for both types of modulation at the same time on the same carrier.
The search and acquisition process for GPS signals, and the reading of the ephemeris and clock data, is time consuming and introduces delays in computing the receiver's position. In addition, there is often blockage of the satellite signals, caused, for example, by building or foliage obscuration, or as a result of operation inside a building where is there is no direct line of sight to any satellite. In these cases, the received signal level can be too low to demodulate and derive the satellite data without error. However, even in these degraded signal situations, the receiver is often still able to track the satellite signals. The measurement of time delay remains possible even at low carrier-power-to-noise-power-density ratios (C/N0). Location solutions may be derived in such cases using aiding data from an external source of ephemeris and time data, for example, supplied by a two-way wireless or cellular communications link. In addition, the time required to acquire the satellite signals and decode the data message may be reduced by accepting versions of the data message from alternative sources such as described above.
GPS aiding requires external knowledge of the absolute time within an accuracy of one to ten milliseconds, so that the satellite positions can be determined accurately. Many wireless communications systems cannot provide this accuracy of time synchronisation. For example, the AMPS cellular phone system does not support time information, nor (currently) does the North American TDMA cellular phone system. The CDMA cellular system supports time aiding as the each base station is operated in a synchronous regime. The CDMA system uses GPS receivers to provide time references which synchronise the CDMA system. The GSM cellular phone system can support timing information, but only with the addition of external equipment (Location Measurement Units, LMUs) because the base stations are asynchronous. Alternatively, Enhanced GPS (EGPS) provides a solution for time transfer in asynchronous systems such as GSM, using the base-station clocks as a repository for GPS time, once acquired. The stability of these clocks has been shown to provide acceptable time recovery almost indefinitely. At the same time, EGPS allows each mobile station (MS) to roam in the network whilst carrying its own position. If required, EGPS ranging capabilities allow for the determination of the MS position and the calibration of previously un-calibrated base-station clocks
Each transmitted GPS signal is a direct-sequence spread-spectrum signal. Broadcasts are made currently on two frequencies denoted L1 (1575.42 MHz) and L2 (1227.60 MHz). Some of these signals have been made available for civil use and are known as the Standard Positioning Service. Mostly available on L1, these utilize a spreading code with a 1.023 MHz spreading rate. Each satellite transmits its own unique pseudo-random code (drawn from a family of so-called Gold codes) that identifies the particular satellite, and allows signals transmitted simultaneously from several satellites to be received simultaneously by a single receiver with little interference to any one signal by the others. The C/A pseudo-random number (PRN) code sequence length is 1023 chips, corresponding to a one-millisecond time period. Each received GPS signal is constructed from the repetitive PRN pattern of 1023 chips transmitted at a rate of 1.023 MHz. At very low signal levels the PRN pattern may still be observed to provide unambiguous time delay measurements through averaging many PRN frames. The transmission time delays measured at the receiver are called “sub-millisecond pseudo-ranges”, since they are known modulo the one millisecond PRN sequence frame boundaries.
A minimum of four pseudo-ranges, together with the transmissions times, is sufficient to solve for the position of the GPS receiver. In the GPS system, the times of transmission are broadcast from the satellites in the navigation message, superimposed on the 1.023 MHz PRN code at a data rate of 50 Hz. This is a BPSK data stream with data-bit transitions aligned with the beginning of the PRN frame. There are exactly 20 PRN code frames per data bit period.
The satellite transmission time is determined in conventional GPS receivers by reading the time-of-week (TOW) data in the GPS navigation message. In the standard method of time determination, a conventional GPS receiver decodes and synchronizes with the 50-Hz data stream. The data signal is arranged into 30-bit words grouped into sub-frames of 10 words, with a length of 300 bits and a duration of six seconds. Five sub-frames comprise a frame of 1500 bits and a duration of 30 seconds, and 25 frames comprise a super-frame with a duration of 12.5 minutes.
The GNSS receiver must initiate an acquisition process to establish coarse parameters describing the states of the received satellite signals. These parameters are used to initialise higher-precision signal-parameter estimation through the use of signal-tracking loops. The higher-precision parameters are then used in the navigation solution. Conventionally, the processing is carried out in dedicated hardware, often consisting of banks of correlators, in order to complete the acquisition process within a reasonable time. Such hardware may be an expensive addition to a mass-market terminal such as a mobile phone. However, some or all of this processing may also be performed in a general-purpose processor provided in the mobile phone. Crucial to the success of such an implementation is the efficient use of the processor design, to best conform with the size of its registers, the particulars of its instruction set, and the capabilities of its data-bus.
In the known prior art, e.g. U.S. Pat. No. 7,010,060 (Ledvina et al.), a real-time software receiver is disclosed which uses so-called “bit-wise parallelism” to perform the functions of hardware correlation, base-band mixing and PRN code correlation using data acquisition and correlator modules which operate on a general purpose processor. Ledvina et al. teach an RF processor producing digitised signal samples of a received signal containing the transmissions from visible GPS satellites. Plural signal samples are processed simultaneously by placing them sequentially in a given word of computer data memory, and then in additional words. For example, if the computer word has 32 bits and the digitised GPS signal samples have been converted using a 1-bit analogue-to-digital converter (ADC), then 32 samples in sequence can be stored in each computer data memory word. Samples of a satellite signal replica are tabulated or generated in real time and can be indexed to provide rapid access. Bit-wise parallelism saves computational time by enabling a required operation, say between a set of input data samples and a stored satellite signal replica, to be performed as an operation between two words, rather than the bits or samples individually.
In forming the algorithms required in a bit-wise parallelism regime, there is a complicated set of register allocation algorithms which is also required. Furthermore, the computation of the correlation sums has to be done by a computationally-intensive method. There is a need to reduce further the processor load and it is therefore a goal of the present invention to eliminate or reduce the computation burden of a number of these tasks.